/***************************************************************************************
 * Copyright (c) 2014-2022 Zihao Yu, Nanjing University
 *
 * NEMU is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan
 *PSL v2. You may obtain a copy of Mulan PSL v2 at:
 *          http://license.coscl.org.cn/MulanPSL2
 *
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY
 *KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
 *NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 *
 * See the Mulan PSL v2 for more details.
 ***************************************************************************************/

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */

#include <isa.h>
#include <memory/vaddr.h>
#include <regex.h>
#include <string.h>

enum {
  TK_NOTYPE = 256,
  TK_EQ,
  TK_HEX,
  TK_NUM,
  TK_REG_$0,
  TK_REG_RA,
  TK_REG_SF,
  TK_REG_GP,
  TK_REG_TF,
  TK_REG_AF,
  TK_AND,
  TK_OR,
  TK_NEQ,
  TK_DEREF,
  TK_NEGNUM,

  /* TODO: Add more token types */
};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

    /* TODO: Add more rules.
     * Pay attention to the precedence level of different rules.
     */
    {"0[xX][0-9a-fA-F]+", TK_HEX}, // hex number
    {"[0-9]+", TK_NUM},            // integer
    {" +", TK_NOTYPE},             // spaces
    {"\\+", '+'},                  // plus
    {"==", TK_EQ},                 // equal
    {"-", '-'},                    // minus
    {"\\*", '*'},                  // multiply
    {"/", '/'},                    // divide
    {"\\(", '('},                  // left bracket
    {"\\)", ')'},                  // right bracket
    {"\\$0", TK_REG_$0},
    {"\\$ra", TK_REG_RA},
    {"\\$gp", TK_REG_GP},
    {"\\$t[0-6p]", TK_REG_TF},
    {"\\$a[0-7]", TK_REG_AF},
    {"\\$s([0-9]|1[01]|p)", TK_REG_SF},
    {"\\&\\&", TK_AND},
    {"\\|\\|", TK_OR},
    {"!=", TK_NEQ},
    {"\\!", '!'}};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used)) = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 &&
          pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s", i,
            rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type) {
        case TK_NOTYPE:
          break;
        // number and register
        case TK_HEX:
        case TK_NUM:
        case TK_REG_$0:
        case TK_REG_RA:
        case TK_REG_GP:
        case TK_REG_TF:
        case TK_REG_AF:
        case TK_REG_SF:
          tokens[nr_token].type = rules[i].token_type;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          nr_token++;
          break;

        case '+':
        case '*':
        case '/':
        case '(':
        case ')':
        case '!':
        case TK_EQ:
        case TK_NEQ:
        case TK_AND:
        case TK_OR:
          tokens[nr_token].type = rules[i].token_type;
          nr_token++;
          break;

        case '-':
          if (nr_token == 0 || ((tokens[nr_token - 1].type != TK_NUM) &&
                                (tokens[nr_token - 1].type != ')'))) {
            tokens[nr_token].type = TK_NEGNUM;
          } else {
            tokens[nr_token].type = '-';
          }
          nr_token++;
          break;

        default:
          TODO();
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

bool check_parentheses(int p, int q, bool *success) {
  if (tokens[p].type != '(' || tokens[q].type != ')') {
    return false;
  }
  int cnt = 0;
  for (int i = p + 1; i < q; i++) {
    if (tokens[i].type == '(') {
      cnt++;
    } else if (tokens[i].type == ')') {
      cnt--;
    }
    if (cnt < 0) {
      *success = false;
      return false;
    }
  }
  if (cnt == 0) {
    return true;
  } else {
    *success = false;
    return false;
  }
}

int get_priority(int type) {
  switch (type) {
  case TK_OR:
    return 0;
  case TK_AND:
    return 1;
  case TK_EQ:
  case TK_NEQ:
    return 2;
  case '+':
  case '-':
    return 3;
  case '*':
  case '/':
    return 4;
  case '!':
    return 100;
  default:
    return -1;
  }
}

int get_dominant_operator(int p, int q) {
  // if expression has ( or ), use cnt
  int split = -1;
  bool valid = true, first = true;
  for (int i = p; i <= q; i++) {
    if (tokens[i].type == '(') {
      valid = false;
      continue;
    }
    if (tokens[i].type == ')') {
      valid = true;
      continue;
    }
    if (valid && get_priority(tokens[i].type) != -1 &&
        get_priority(tokens[i].type != 100)) {
      if (first ||
          get_priority(tokens[i].type) <= get_priority(tokens[split].type)) {
        split = i;
        first = false;
      }
    }
  }
  return split;
}

static inline char *get_sub_str(char *str, int p, int q) {
  char *sub_str = (char *)malloc(sizeof(char) * (q - p + 2));
  for (int i = p; i <= q; i++) {
    sub_str[i - p] = str[i];
  }
  sub_str[q - p + 1] = '\0';
  return sub_str;
}

#define gpr(i) cpu.gpr[i]

word_t eval(int p, int q, bool *success) {
  if (p > q) {
    *success = false;
    return -1;
  } else if (p == q) {
    switch (tokens[p].type) {
    case TK_HEX:
      return strtol(tokens[p].str, NULL, 16);
    case TK_NUM:
      return strtol(tokens[p].str, NULL, 10);
    case TK_REG_$0:
      return gpr(0);
    case TK_REG_RA:
    case TK_REG_GP:
    case TK_REG_TF:
    case TK_REG_AF:
    case TK_REG_SF:
      char *reg_name1 =
          get_sub_str(tokens[p].str, 1, strlen(tokens[p].str) - 1);
      return isa_reg_str2val(reg_name1, success);
    default:
      return 0;
    }
  } else if (check_parentheses(p, q, success) == true) {
    return eval(p + 1, q - 1, success);
  } else {
    int op = get_dominant_operator(p, q);
    if (op != -1) {
      word_t val1 = eval(p, op - 1, success);
      word_t val2 = eval(op + 1, q, success);
      switch (tokens[op].type) {
      case '+':
        return val1 + val2;
      case '-':
        return val1 - val2;
      case '*':
        return val1 * val2;
      case '/':
        if (val2 == 0) {
          *success = false;
          return 0;
        }
        return val1 / val2;
      case TK_EQ:
        return val1 == val2;
      case TK_NEQ:
        return val1 != val2;
      case TK_AND:
        return val1 && val2;
      case TK_OR:
        return val1 || val2;
      default:
        return 0;
      }
    } else {
      switch (tokens[p].type) {
      case TK_DEREF:
        return vaddr_read(eval(p + 1, q, success), 4);
      case '!':
        return !eval(p + 1, q, success);
      case TK_NEGNUM:
        return -eval(p + 1, q, success);
      default:
        *success = false;
        return 0;
      }
    }
  }
}

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  for (int i = 0; i < nr_token; i++) {
    if (tokens[i].type == '*' &&
        (i == 0 || tokens[nr_token - 1].type == '+' ||
         tokens[nr_token - 1].type == '-' || tokens[nr_token - 1].type == '*' ||
         tokens[nr_token - 1].type == '/' || tokens[nr_token - 1].type == '(' ||
         tokens[nr_token - 1].type == TK_EQ ||
         tokens[nr_token - 1].type == TK_NEQ ||
         tokens[nr_token - 1].type == TK_AND ||
         tokens[nr_token - 1].type == TK_OR ||
         tokens[nr_token - 1].type == '!' ||
         tokens[nr_token - 1].type == TK_NEGNUM ||
         tokens[nr_token - 1].type == TK_DEREF)) {
      tokens[i].type = TK_DEREF;
    }
  }

  return eval(0, nr_token - 1, success);
}
